//Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
// determine if the input string is valid. 
//
// An input string is valid if: 
//
// 
// Open brackets must be closed by the same type of brackets. 
// Open brackets must be closed in the correct order. 
// 
//
// Note that an empty string is also considered valid. 
//
// Example 1: 
//
// 
//Input: "()"
//Output: true
// 
//
// Example 2: 
//
// 
//Input: "()[]{}"
//Output: true
// 
//
// Example 3: 
//
// 
//Input: "(]"
//Output: false
// 
//
// Example 4: 
//
// 
//Input: "([)]"
//Output: false
// 
//
// Example 5: 
//
// 
//Input: "{[]}"
//Output: true
// 
// Related Topics 栈 字符串


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    fun isValid(s: String): Boolean {
        val stack = Stack<Char>()
        for (c in s) {
            when(c){
                '(','[','{' -> stack.push(c)
                else ->{
                    if (stack.empty()) {
                        return false
                    }
                    val top = stack.pop()
                    val curValid = when(c){
                        ')'->top == '('
                        ']'->top == '['
                        else->top == '{'
                    }
                    if (!curValid) {
                        return false
                    }
                }
            }
        }

        return stack.empty()
    }
}
//leetcode submit region end(Prohibit modification and deletion)
